#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include"xh.h"
HashTable InitializeTable(int TableSize) {
	int i = 0;
	if (TableSize < MinTableSize) {
		TableSize = MinTableSize;
	}

	HashTable H = malloc(sizeof(struct HashTbl));
	if (H == NULL) {
		perror("malloc");
		return NULL;
	}
	H->TableSize = Nextprime(TableSize);

	H->TheLists = malloc(sizeof(List) * H->TableSize);
	if (H->TheLists == NULL) {
		perror("malloc");
		free(H);
		return NULL;
	}
	for (i = 0; i < H->TableSize; i++) {
		H->TheLists[i] = malloc(sizeof(Position));
		if (H->TheLists[i] == NULL)
			printf("space is error!");
		else
			H->TheLists[i]->Next = NULL;
	}
	return H;
}

Position Find(ElementType Key, HashTable H) {
	List head = H->TheLists[Hash(H->TableSize, Key)];
	Position Pos = head->Next;

	while (Pos != NULL && Pos->Element != Key) {
		Pos = Pos->Next;
	}

	return Pos;
}

void Insert(ElementType Key, HashTable H) {
	Position pos, newCell;
	List head;
	pos = Find(Key, H);
	if (pos == NULL) {
		newCell = malloc(sizeof(struct ListNode));
		if (newCell == NULL) {
			perror("malloc");
			return;
		}
		head = H->TheLists[Hash(H->TableSize, Key)];
		newCell->Next = head->Next;
		newCell->Element = Key;
		head->Next = newCell;
	}
}

ElementType Retrieve(Position pos) {
	return pos->Element;
}


void DestroyTable(HashTable H) {
	if (H == NULL) {
		return;
	}

	int i = 0;
	Position temp;
	for (i = 0; i < H->TableSize; i++) {
		List head = H->TheLists[i];
		while (head != NULL) {
			temp = head->Next;
			free(head);
			head = temp;
		}
	}
}

Index Hash(int TableSize, ElementType key) {
	return key % TableSize;
}

int isprime(int N) {
	int i = 0;
	if (N == 2 || N == 3)
		return 1;
	if (N % 2 == 0)
		return 0;
	else
		for (i = 3; i * i < N; i += 2)
		{
			if (N % i == 0)
				return 0;
		}
	return 1;
}
int Nextprime(int N) {
	while(!isprime(N)){
		N++;
	}

	return N;
}